﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using Multiprocessing.Core.Algorithm;
using Multiprocessing.Core.Units;

namespace Multiprocessing.Algorithms.Sorting
{
    internal sealed class SortArrayInfo
    {
        #region Fields

        private readonly Array _arrayToSort;
        private readonly int _segmentStartIndex;
        private readonly int _segmentLength;

        #endregion

        #region Properties

        internal Array ArrayToSort 
        { 
            get { return _arrayToSort; }
        }

        internal int SegmentStartIndex
        {
            get { return _segmentStartIndex; }
        }

        internal int SegmentLength 
        { 
            get { return _segmentLength; }
        }

        #endregion

        #region Constructors

        internal SortArrayInfo(Array arrayToSort, int segmentStartIndex, int segmentLength)
        {
            if (ReferenceEquals(arrayToSort, null))
            {
                throw new ArgumentNullException("arrayToSort");
            }
            _arrayToSort = arrayToSort;
            _segmentLength = segmentLength;
            _segmentStartIndex = segmentStartIndex;
        }

        #endregion

        #region Methods

        internal Action GetSortAction()
        {
            return () => Array.Sort(ArrayToSort, SegmentStartIndex, SegmentLength);
        }

        #endregion
    }

    public class DoublingSortingAlgorithm : BaseAlgorithm<int[]>
    {
        #region Constructor
        
        public DoublingSortingAlgorithm(IProcessingBlockFactory processingBlockFactory, string name)
            : base(processingBlockFactory, name)
        {
        }

        public DoublingSortingAlgorithm(string name) : base(ProcessingBlockFactory.Instance, name)
        {
        }

        #endregion

        #region Methods

        public override object[] CreateParameters(int size)
        {
            int [] result = new int[size];
            Random rand = new Random();
            for (int i = 0; i < size; ++i)
            {
                result[i] = rand.Next();
            }
            return new object[] {result};
        }

        public override AlgorithmResult<int[]> Execute(IProcessingBlock processingBlock, params object[] args)
        {
            return this.Execute(processingBlock, (int[]) args[0]);
        }

        public AlgorithmResult<int[]> Execute(IProcessingBlock processingBlock, int[] array)
        {
            if (ReferenceEquals(processingBlock, null))
            {
                throw new ArgumentNullException("processingBlock");
            }
            if (ReferenceEquals(array, null))
            {
                throw new ArgumentNullException("array");
            }
            // use quick sort for simple arrays
            // array.sort
            int[] temp = new int[array.Length];
            array.CopyTo(temp, 0);
            int valuesPerUnit = temp.Length / processingBlock.Size,
                rest = temp.Length % processingBlock.Size;

            // list to save information about subarrays
            var arraySegmentList = new LinkedList<SortArrayInfo>();

            // 1. sort subarrays
            int unitIdx = 0;
            for (unitIdx = 0; unitIdx < processingBlock.Size - 1; ++unitIdx)
            {
                var segmentInfo = new SortArrayInfo(temp, unitIdx*valuesPerUnit, valuesPerUnit);
                arraySegmentList.AddLast(segmentInfo);
                processingBlock[unitIdx] = segmentInfo.GetSortAction();
            }
            // last part sorted with rest
            var lastSegmentInfo = new SortArrayInfo(temp, unitIdx*valuesPerUnit, valuesPerUnit + rest);
            arraySegmentList.AddLast(lastSegmentInfo);
            processingBlock[unitIdx] = lastSegmentInfo.GetSortAction();
            
            this.Stopwatch.Restart();
            processingBlock.StartAll();
            processingBlock.WaitAll();
            this.Stopwatch.Stop();
            // merge subarrays;

            // mulitplier of unit (2, 4, 8, 16...)
            for (int multiplier = 2; multiplier < processingBlock.Size; multiplier <<= 1)
            {
                // new subarrays
                LinkedList<SortArrayInfo> newListInfo = new LinkedList<SortArrayInfo>();
                // list of units to start
                List<int> unitsToStart = new List<int>();
                for (int i = 0; i < processingBlock.Size / multiplier; ++i)
                {
                    // get two part to merge
                    var firstPart = arraySegmentList.First.Value;
                    arraySegmentList.RemoveFirst();
                    var secondPart = arraySegmentList.First.Value;
                    arraySegmentList.RemoveFirst();
                    // set an action to merge
                    unitIdx = i * multiplier;
                    processingBlock[unitIdx] =
                        () =>
                        Merge(temp, firstPart.SegmentStartIndex, firstPart.SegmentLength, secondPart.SegmentStartIndex,
                              secondPart.SegmentLength);
                    // save unit idx to start
                    unitsToStart.Add(unitIdx);
                    newListInfo.AddLast(new SortArrayInfo(temp, firstPart.SegmentStartIndex,
                                                          firstPart.SegmentLength + secondPart.SegmentLength));
                }
                this.Stopwatch.Start();
                unitsToStart.ForEach(processingBlock.StartOne);
                unitsToStart.ForEach(processingBlock.WaitOne);
                this.Stopwatch.Stop();
                // if we have some parts of arrays - send it to next iteration level
                if (arraySegmentList.Any())
                {
                    newListInfo.AddLast(arraySegmentList.First.Value);
                }
                arraySegmentList = newListInfo;
            }

            if (arraySegmentList.Count == 2)
            {
                var firstPart = arraySegmentList.First.Value;
                arraySegmentList.RemoveFirst();
                var secondPart = arraySegmentList.First.Value;
                arraySegmentList.RemoveFirst();
                // set an action to merge
                processingBlock[0] =
                    () =>
                    Merge(temp, firstPart.SegmentStartIndex, firstPart.SegmentLength, secondPart.SegmentStartIndex,
                          secondPart.SegmentLength);
                this.Stopwatch.Start();
                processingBlock.StartOne(0);
                processingBlock.WaitOne(0);
                this.Stopwatch.Stop();
            }


            return new AlgorithmResult<int[]>(temp, this.Stopwatch.Elapsed, -1);
        }

        private static void Merge(int[] array, int firstSegmentStart, int firstSegmentLength, int secondSegmentStart, int secondSegmentLength)
        {
            int firstIndex = firstSegmentStart,
                secondIndex = secondSegmentStart,
                firstFinish = firstSegmentStart + firstSegmentLength,
                secondFinish = secondSegmentStart + secondSegmentLength,
                mergedIndex = 0;
            int[] merged = new int[firstSegmentLength + secondSegmentLength];

            while (firstIndex + secondIndex < firstFinish + secondFinish)
            {
                if (secondIndex >= secondFinish || (firstIndex < firstFinish && array[firstIndex] <= array[secondIndex]))
                {
                    merged[mergedIndex] = array[firstIndex];
                    firstIndex++;
                }
                else
                {
                    merged[mergedIndex] = array[secondIndex];
                    secondIndex++;
                }
                mergedIndex++;
            }
            Array.Copy(merged, 0, array, firstSegmentStart, firstSegmentLength );
            Array.Copy(merged, firstSegmentLength, array, secondSegmentStart, secondSegmentLength);
        }

        #endregion
    }
}
